// #define print(...)
#ifdef USE_DFS
using it_t = vector<int>::iterator;
class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
		auto const n = nums.size();
		vector<bool> in(n, false);
		vector<int> ans(n, -1);
		bool solved = false;
		function<void(it_t)> dfs = [&](it_t it){
			print(it-ans.begin(), ans, in, "\n")
			if(it-ans.begin()>=3){
				if( *(it-1) + *(it-3) == ((*(it-2))<<1) )
					return;
				if(it == ans.end()){
					solved = true;
					return;
				}
			}
			if(it == ans.end()) return;
			for(size_t i=0; !solved && i<n; i++){
				if(in[i]) continue;
				*it = nums[i];
				in[i] = true;
				dfs(it+1);
				in[i] = false;
			}
		};
		dfs(ans.begin());
		print("solved:", solved, ", ")
		return ans;
    }
};
#else
class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		auto const n = nums.size();
		vector<int> ans(n);
		auto m = (n+1)/2;
		for(size_t i=0; i<m; i++){
			ans[2*i] = nums[i];
			if(m+i<n)
				ans[2*i+1] = nums[m+i];
		}
		return ans;
	}
};
#endif